\BfPara{Any solution to Program \ref{lp_with_mins} is an exact personalized
  equilibrium} Assume we have a solution to
Equation~\ref{lp_with_mins} that is not a personalized
equilibrium. The first two constraints ensure that our solution is a
feasible weight assignment for the game. Therefore, there must be some
player $i$ who is not playing a best response. Take some better
response, in which player $i$ plays weights $w_i^*(e)$, and let
$\delta(e) = w^*_i(e) - w_i(e)$.

Let $F$ be the subset of $E_i$ such that $\delta(e) < 0$ (that is,
player $i$ puts more weight on each edge in $F$ in the original
response than in the best response). Since $w_i^*$ has a strictly
higher total utility for player $i$ than $w_i$, we know that $\sum_{e
  \in E_i} w^*_i(e) u_i(e) > \sum_{e \in E_i} w_i(e) u_i(e)$, which
implies that $\sum_{e \in E_i} \delta(e) u_i(e) > 0$.  Since both $w_i$
and $w^*_i$ were feasible weights, it must be true for any strategy
$s$ that $\sum_{e:s \in e} w_i(e) = \sum_{e: s \in e} w^*_i(e)
\Rightarrow \sum_{e: s \in e} \delta(e) = 0$.

By our definition of $F$, $\delta(e) < 0$ for all $e \in F$ and
$\delta(e) \geq 0$ for all $e \notin F$. Therefore, $F$ and $i$ obey
all the constraints of linear program \ref{non_optimal_lp}, so since
$w_i(e)$ obeyed program \ref{lp_with_mins}, we know that $\min_{e \in
  F} w_i(e) = 0$. Thus, there exists some edge $f \in F$ such that
$w_i(f) = 0$. Then $0 > \delta(f) = w^*_i(f) - w_i(f) = w^*_i(f)$,
contradicting the fact that $w^*_i$ was a feasible best response for
player $i$.  
\smallskip

\BfPara{Any personalized equilibrium is a solution to Program \ref{lp_with_mins}}
Assume we have a personalized equilibrium that does not satisfy some
constraint of Program \ref{lp_with_mins}. Let $w_i(e)$ be the weight placed by player
$i$ on edge $e$ in this equilibrium. The first three constraints
are the definition of a feasible weight assignment and therefore must hold for any personalized equilibrium. Therefore, assume
this equilibrium does not satisfy the $\min$ constraint for some
player $i$ and some subset $F \subseteq E_i$ for which LP
\ref{non_optimal_lp} is feasible.

Consider a solution $\delta$ for LP \ref{non_optimal_lp} for this $i$
and $F$. Let $M = \frac{\min_{e \in F} |w_i(e)|}{\max_{e \in F}
  |\delta(e)|}$, and let $\delta'(e) = (\delta(e) \cdot M)$. $M$ is a
well-defined positive number since (1) the $\min$ constraint was not
satisfied, by our choice of $i$ and $F$, so $\min_{e \in F} |w_i(e)| > 0$, and (2) LP \ref{non_optimal_lp} specifies that $\delta(e) <
0$ for all $e \in F$, so $\max_{e \in F} |\delta(e)| > 0$. We know that $F$ is non-empty because the first constraint implies there is some $\delta > 0$, and combining this with the second constraint implies there is also some $\delta < 0$. Furthermore, for all $e$ with $\delta(e)<0$
(i.e., for all $e \in F$), $|\delta'(e)| \leq w_i(e)$. Now, consider
the alternate assignment for player $i$ specified by $w^*_i(e) =
w_i(e) + \delta'(e)$.  By the second constraint of LP
\ref{non_optimal_lp} and the fact that $|\delta'(e)| \leq w_i(e)$ for
all $e$ with $\delta(e) <0$, this is still a valid weight
assignment. By the first constraint of LP \ref{non_optimal_lp}, this
gives a strictly higher total utility for player $i$. Therefore,
weights $w_i(e)$ did not give a best response for player $i$, so we
did not have a personalized equilibrium, contradicting our assumption
and completing the proof.